/*
 * @lc app=leetcode.cn id=355 lang=javascript
 *
 * [355] 设计推特
 */

// @lc code=start

// 堆base
class PQ {
  /**
   * @description: PQ基类构造函数
   * @param {[any]} keys
   * @param {function} mapKeysValue
   * @return {void}
   */
  constructor(keys = [], mapKeysValue = (x) => x) {
    this.keys = [...keys];
    this.mapKeysValue = mapKeysValue;
    // 初始化一下keys的排序
    for (let i = (this.keys.length - 2) >> 1; i >= 0; i--) {
      this.sink(i);
    }
  }

  /**
   * @description: 比较i元素是否小于j元素
   * @param {number} i
   * @param {number} j
   * @return {boolean}
   */
  less(i, j) {
    return this.mapKeysValue(this.keys[i]) < this.mapKeysValue(this.keys[j]);
  }
  /**
   * @description: 交换i和j元素
   * @param {number} i
   * @param {number} j
   * @return {void}
   */
  exch(i, j) {
    [this.keys[i], this.keys[j]] = [this.keys[j], this.keys[i]];
  }

  /**
   * @description: 元素上浮
   * @param {number} index 需要上浮元素的索引
   * @return {void}
   */
  swin(index) {
    let parent = (index - 1) >> 1;
    while (parent >= 0 && this.less(parent, index)) {
      this.exch(parent, index);
      index = parent;
      parent = (parent - 1) >> 1;
    }
  }

  /**
   * @description: 元素下沉
   * @param {number} index 需要下沉元素的索引
   * @return {void}
   */
  sink(index) {
    let child = index * 2 + 1;
    let len = this.keys.length;
    while (child < len) {
      if (child + 1 < len && this.less(child, child + 1)) {
        child++;
      }
      if (this.less(child, index)) break;

      this.exch(child, index);
      index = child;
      child = index * 2 + 1;
    }
  }
  /**
   * @description: 堆的大小
   * @return {number}
   */
  size() {
    return this.keys.length;
  }
  /**
   * @description: 插入操作
   * @param {any} key
   * @return {void}
   */
  insert(key) {
    this.keys.push(key);
    this.swin(this.keys.length - 1);
  }
  /**
   * @description: 删除顶部元素
   * @return {any}
   */
  poll() {
    let head = this.peek();
    this.exch(0, this.size() - 1);
    this.keys.pop();
    this.sink(0);
    return head;
  }
  /**
   * @description: 查看顶部元素
   * @return {any}
   */
  peek() {
    return this.keys[0];
  }
}
// 大顶堆
class MaxPQ extends PQ {}

// 用户
class User {
  // 发送推文的时间戳
  static timestamp = new Date().getTime();
  constructor(userID) {
    this.id = userID;
    // 关注的用户
    this.follows = new Set();
    // 发送的推文
    this.tweets = [];
  }

  /**
   * @description: 发送推文
   * @param {number} tweetID
   * @return {void}
   */
  post(tweetID) {
    const tweet = new Tweet(tweetID, User.timestamp++);
    this.tweets.push(tweet);
  }
  /**
   * @description: 关注用户
   * @param {number} userID
   * @return {void}
   */
  follow(userID) {
    this.follows.add(userID);
  }
  /**
   * @description: 取消关注
   * @param {number} userID
   * @return {void}
   */
  unfollow(userID) {
    this.follows.delete(userID);
  }
}

// 推文
class Tweet {
  constructor(tweetID, timestamp) {
    this.id = tweetID;
    this.timestamp = timestamp;
  }
}

/**
 * Initialize your data structure here.
 */
var Twitter = function () {
  // 模拟数据库存储的用户
  this.users = new Map();
};

/**
 * Compose a new tweet.
 * @param {number} userId
 * @param {number} tweetId
 * @return {void}
 */
Twitter.prototype.postTweet = function (userId, tweetId) {
  // 如果库中没有用户，新建一个
  if (!this.users.has(userId)) {
    this.users.set(userId, new User(userId));
  }
  const user = this.users.get(userId);
  user.post(tweetId);
};

/**
 * Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
 * @param {number} userId
 * @return {number[]}
 */
Twitter.prototype.getNewsFeed = function (userId) {
  // 库中没查询到用户
  if (!this.users.has(userId)) {
    return [];
  }
  // 当前用户和他关注的用户
  const userIDs = [userId, ...this.users.get(userId).follows];
  // 取出用户列表中所有用户发送的tweet
  const twwers = [];
  for (let idx of userIDs) {
    let user = this.users.get(idx);
    twwers.push(...user.tweets);
  }
  // 放入大顶堆，按照时间从大到小
  const maxPQ = new MaxPQ(twwers, (x) => x.timestamp);
  const result = [];
  // 取前10条最新的数据
  while (result.length < 10 && maxPQ.size()) {
    result.push(maxPQ.poll().id);
  }

  return result;
};

/**
 * Follower follows a followee. If the operation is invalid, it should be a no-op.
 * @param {number} followerId
 * @param {number} followeeId
 * @return {void}
 */
Twitter.prototype.follow = function (followerId, followeeId) {
  if (!this.users.has(followerId)) {
    this.users.set(followerId, new User(followerId));
  }
  if (!this.users.has(followeeId)) {
    this.users.set(followeeId, new User(followeeId));
  }
  const user = this.users.get(followerId);
  user.follow(followeeId);
};

/**
 * Follower unfollows a followee. If the operation is invalid, it should be a no-op.
 * @param {number} followerId
 * @param {number} followeeId
 * @return {void}
 */
Twitter.prototype.unfollow = function (followerId, followeeId) {
  if (this.users.has(followerId)) {
    const user = this.users.get(followerId);
    user.unfollow(followeeId);
  }
};

/**
 * Your Twitter object will be instantiated and called as such:
 * var obj = new Twitter()
 * obj.postTweet(userId,tweetId)
 * var param_2 = obj.getNewsFeed(userId)
 * obj.follow(followerId,followeeId)
 * obj.unfollow(followerId,followeeId)
 */
// @lc code=end
